/**
 * 
 */
package tamago.csp.stringbuilder.automaton;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Hashtable;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

import tamago.csp.exception.TamagoCSPException;
import tamagocc.logger.TamagoCCLogger;
import tamagocc.util.Pair;

/**
 * This class represents the abstract automaton (NFA or DFA).
 * This automaton creats own states and keep an array of all created states.
 * Furthermore it allows the definition of multiple final states.
 * Here we assume that information are remain on transition, and the existence
 * of at leat one final state.
 * 
 * @author Hakim Belhaouari
 * @see SState, SAbsTransition
 */
public class SAuto {

	private SState init;
	private Set<SState> finals;	
	private ArrayList<SState> states;
	private int ids;	

	/**
	 * Default constructor. Creat an empty automaton.
	 *
	 */
	public SAuto() {
		this.init = null;
		this.finals = new TreeSet<SState>();
		states =new ArrayList<SState>();
		ids = 0;
	}

	/**
	 * This method allow the creation and registration of one state for the current
	 * automaton. The first created state is set as the initial state. However we can 
	 * redefine it in the future.
	 * 
	 * @return return a new created state.
	 */
	public SState creatState() {
		if(ids == 0) {
			init = new SState(ids);
			states.add(init);
			ids++;
			return init;
		}
		else{ 
			SState renvoie = new SState(ids++);
			states.add(renvoie);
			return renvoie;
		}
	}

	/**
	 * Indicates if a state owned by the current automaton is a final state.
	 * @param s : state associate to the current automaton
	 * @return return true is the state is a final state in the current automaton
	 */
	public boolean isFinalState(SState s) {
		return finals.contains(s);
	}

	/**
	 * Add a new state (owned by this current automaton) to the set of final state
	 * @param s
	 */
	public void addFinalState(SState s) {
		finals.add(s);
	}
	

	/**
	 * Indicates if the automaton satisfies a word.
	 * @param txt : word to check
	 * @return return true is the word is accepted by the automaton
	 */
	public boolean isAccepted(String txt) {
		return run(txt,0,init);
	}

	private boolean run(String str,int k, SState q) {
		if(k >= str.length()) {
			TreeSet<SState> states = new TreeSet<SState>();
			getAccessibleState(states, q);
			for (SState state : states) {
				if(finals.contains(state))
					return true;
			}
			return false;
		}
		else {
			char c = str.charAt(k);
			for(SAbsTransition trans : getAccessibleTransition(q)) {
				if(trans.accept(c) && run(str,k+1,trans.getEnd()) ) {
					return true;
				}
			}
			return false;
		}
	}

	/**
	 * Accessor of all states
	 * @return An iterable element containing all states
	 */
	public Iterable<SState> getStates() {
		return states;
	}

	/**
	 * This method try to find the minimal size of the string generated by the
	 * automaton given in argument.
	 * @param auto: automaton
	 * @return return the min size, and -1 if an error occur.
	 */
	public static int evalMinSize(SAuto auto) {
		try {
			return evalMinSize(auto, auto.init);
		}
		catch(Exception ex) {
			return -1;
		}
	}

	private static int evalMinSize(SAuto auto,SState etat) {
		int min = -1;
		Stack<Pair<SState, Integer>> pile = new Stack<Pair<SState,Integer>>();

		TreeSet<SState> states = new TreeSet<SState>();
		getAccessibleState(states, etat);
		for (SState state : states) {
			if(auto.isFinalState(state))
				return 0;
		}
		states = new TreeSet<SState>();
		pile.push(new Pair<SState, Integer>(etat, 0));
		
		while(pile.size() > 0) {
			//TamagoCCLogger.println(4,"Taille evalMin:"+pile.size());
			Pair<SState, Integer> pair = pile.pop();
			int prof = pair.r().intValue();
			if(auto.isFinalState(pair.l())) {
				if(min == -1) 
					min = prof;
				else if(prof < min)
					prof  = min;
			}
			else {
				if(!states.contains(pair.l())) {
					states.add(pair.l());
					Collection<STransition> trans = getAccessibleTransition(pair.l());
					for (STransition transition : trans) {
						pile.push(new Pair<SState, Integer>(transition.getEnd(), prof+1));
					}
				}
			}
		}
		return min; // error
	}
	

	private static int evalMaxSize(SAuto auto,SState etat) {
		int max = -1;
		Stack<Pair<SState, Integer>> pile = new Stack<Pair<SState,Integer>>();
		TreeSet<SState> marked = new TreeSet<SState>();
		
		TreeSet<SState> states = new TreeSet<SState>();
		getAccessibleState(states, etat);
		for (SState state : states) {
			if(auto.isFinalState(state))
				max = 0;
		}
		pile.push(new Pair<SState, Integer>(etat, 0));
		while(pile.size() > 0) {
			//TamagoCCLogger.println(4,"Taille evalMax:"+pile.size());
			Pair<SState, Integer> pair = pile.pop();
			int prof = pair.r().intValue();
			if(!marked.contains(pair.l())) {
				marked.add(pair.l());
				if(auto.isFinalState(pair.l())) {
					if(max == -1) 
						max = prof;
					else if(prof > max)
						prof  = max;
				}			
				Collection<STransition> trans = getAccessibleTransition(pair.l());
				for (STransition transition : trans) {
					pile.push(new Pair<SState, Integer>(transition.getEnd(), prof+1));
				}
			}
			else
				return -2;
				
		}
		return max; // error
	}
	
	/**
	 * This method try to eval the max size of a generated word from a specific automaton.
	 * @param auto: automaton
	 * @return return the maximal size of a generated word, or return -2 if we detect a cycle and -1 
	 * if an error occur
	 */
	public static int evalMaxSize(SAuto auto) {
		try {
			return evalMaxSize(auto,auto.init);
		}
		catch(Exception e) {
			return -1;
		}
	}

	@SuppressWarnings("unchecked")
	private static int evalMaxSize(SAuto auto,TreeSet<SState> marked, SState etat) {
		int max = -1;
		TreeSet<SState> states = new TreeSet<SState>();
		getAccessibleState(states, etat);
		for (SState state : states) {
			if(marked.contains(state))
				return -2; // cycle detecter
		}
		for (SState state : states) {
			marked.add(state);
		}
		states = null; // plus besoins
		Collection<STransition> trans = getAccessibleTransition(etat);
		for (STransition transition : trans) {
			Object clone2 =  marked.clone();
			TreeSet<SState> clone = (TreeSet<SState>)clone2; // pour retrouver l'etat correct
			int res = evalMaxSize(auto, clone, transition.getEnd());
			if(res == -2)
				return -2; // on trouver un cycle on arrete la
			else if((max == -1) || ((res+1) > max))
				max = (res+1);
		}
		if(max == -1)
			return 0;
		else
			return max;
	}

	public static void getAccessibleState(Set<SState> set, SState a) {
		if(!set.add(a)) 
			return;
		for (SAbsTransition trans : a.getTransitions()) {
			if(trans.isEpsilon()) {
				getAccessibleState(set, trans.getEnd());
			}
		}
	}

	public static Collection<STransition> getAccessibleTransition(SState state) {
		TreeSet<SState> seta = new TreeSet<SState>();
		ArrayList<STransition> trans = new ArrayList<STransition>();

		getAccessibleState(seta, state);

		for (SState s : seta) {
			for (SAbsTransition transition : s.getTransitions()) {
				if(!transition.isEpsilon()) {
					trans.add((STransition) transition);
				}
			}
		}
		return trans;
	}


	/**
	 * Getter of the initial state.
	 * @return return the initial state
	 */
	public SState init() {
		return init;
	}

	/**
	 * Getter of the set of finals states
	 * @return return the set of finals states
	 */
	public Set<SState> getFinals() {
		return finals;
	}

	/**
	 * This method allow user to creat easily pattern of verification. This one creat an empty
	 * automaton, with an initial state.
	 * 
	 * @return an automaton with one initial state.
	 */
	public static SAuto motifEmpty() {
		SAuto auto = new SAuto();
		SState init = auto.creatState();
		auto.addFinalState(init);
		return auto;
	}

	/**
	 * Creat an automaton that accept a pattern 
	 * @param l : the range of accepted character
	 * @return return an automaton
	 */
	public static SAuto motifChar(SLetter l) {
		SAuto auto = new SAuto();
		SState init = auto.creatState();
		SState end = auto.creatState();
		new STransition(init,end,l);
		auto.addFinalState(end);
		return auto;
	}

	/**
	 * Creat an automaton that accept a pattern (SLetter), with a specific redundancy.
	 * This method is not again fully implemented and should considered as an optimisation
	 * in used memory structure
	 * @param l: pattern of accepted characters
	 * @param redundancy: specify the redundancy, 0 means infinite use
	 * @return Return the constructed automaton
	 */
	public static SAuto motifChar(SLetter l, int redundancy) {
		SAuto auto = new SAuto();
		SState init = auto.creatState();
		SState end = auto.creatState();
		new STransition(init,end,l,redundancy);
		auto.addFinalState(end);
		return auto;
	}

	public static SAuto motifRepeatChar(SLetter l, int repeat) {
		SAuto auto = new SAuto();
		SState init = auto.creatState();
		SState cur = init;
		SState next = null;
		for(int i=0; i < repeat;i++) {
			next = auto.creatState();
			new STransition(cur, next, l);
			cur = next;
		}
		auto.addFinalState(cur);
		return auto;
	}

	/**
	 * This method concatenates two automatons
	 * @param p: the first automaton
	 * @param q: the second automaton
	 * @return Return the automaton that begin with p and finish with q
	 */
	public static SAuto motifSequence(SAuto p, SAuto q) {
		SAuto auto = new SAuto();

		// On copie le premier automate
		Collection<SState> newfinals;
		Hashtable<SState, SState> hash = new Hashtable<SState, SState>();
		for(SState s : p.states) {
			hash.put(s, auto.creatState());
		}
		auto.init = hash.get(p.init); // on recalibre l'etat initial au cas ou 

		newfinals = searchMirrorsFinals(hash, p);

		// Ensuite on prepare les etats pour le second
		hash = new Hashtable<SState, SState>();
		for(SState s : q.states) {
			hash.put(s, auto.creatState());
		}

		// pour chaque etat final du premier on cree une transition epsilon
		// puis on recopie l'automate q
		SState tmpini = hash.get(q.init);
		for(SState fin : newfinals) {
			new SEpsTransition(fin,tmpini);
		}

		newfinals = new ArrayList<SState>();
		newfinals = searchMirrorsFinals(hash, q);

		// maintenant on indique les etats finaux
		for(SState fin : newfinals) {
			auto.addFinalState(fin);
		}

		// on renvoit le resultat
		return auto;
	}

	private static ArrayList<SState> searchMirrorsFinals(Hashtable<SState, SState> hash, SAuto p) {
		Stack<SState> pile = new Stack<SState>();
		pile.push(p.init());
		TreeSet<SState> visited = new TreeSet<SState>();
		ArrayList<SState> finals = new ArrayList<SState>();
		while(!pile.isEmpty()) {
			SState s = pile.pop();
			if(!visited.contains(s)) {
				visited.add(s);
				SState mirrorA = hash.get(s);
				if(p.finals.contains(s))
					finals.add(mirrorA);
				for(SAbsTransition transition : s.getTransitions()) {
					SState mirrorB = hash.get(transition.getEnd());
					transition.clone(mirrorA, mirrorB);
					pile.push(transition.getEnd());
				}
			}
		}
		return finals;
	}
	/*
		SState mirrorA = hash.get(state);
		if(visited.contains(state))
			return;
		else
			visited.add(state);

		if(p.finals.contains(state))
			tmp.add(mirrorA);

		for(SAbsTransition transition : state.getTransitions()) {
			SState mirrorB = hash.get(transition.getEnd());
			transition.clone(mirrorA, mirrorB);
			followAutomaton(hash,visited, transition.getEnd(), p, tmp);
		}
	}*/

	/**
	 * Construct an automaton with a choice where the first branch is p
	 * and the second is q.
	 * @param p: first automaton
	 * @param q: second automaton
	 * @return Return an automaton representing the choice of both automaton
	 */
	public static SAuto motifSwitch(SAuto p, SAuto q) {
		SAuto auto = new SAuto();
		SState init = auto.creatState();

		// on prepare la branche superieur
		Collection<SState> newfinals;
		Hashtable<SState, SState> hash = new Hashtable<SState, SState>();
		for(SState s : p.states) {
			hash.put(s, auto.creatState());
		}

		SState tmpini = hash.get(p.init);		
		new SEpsTransition(init,tmpini);
		newfinals = searchMirrorsFinals(hash, p);

		// on prepare la seconde branche
		hash = new Hashtable<SState, SState>();
		for(SState s : q.states) {
			hash.put(s, auto.creatState());
		}

		tmpini = hash.get(q.init);		
		new SEpsTransition(init,tmpini);
		newfinals = searchMirrorsFinals(hash, q);

		// maintenant newfinals contient tous les etats terminaux que l'on va fusionner
		SState end = auto.creatState(); 
		for(SState fin : newfinals) {
			new SEpsTransition(fin,end);
		}

		// affect end
		auto.addFinalState(end);

		// on renvoit le resultat
		return auto;
	}

	/**
	 * Creat an automaton that accept any string.
	 * @return Return an automaton that accept everything
	 */
	public static SAuto motifAny() {
		SAuto auto = new SAuto();
		SState init = auto.creatState();
		SState end = auto.creatState();
		new STransition(init,end,new SAnyLetter());
		new SEpsTransition(end,init);
		new SEpsTransition(init,end);
		auto.addFinalState(end);
		auto.addFinalState(init);
		return auto;
	}


	/**
	 * Creat an automaton that repeat infinitly the automaton p
	 * @param p: the automaton to be repeated
	 * @return Return the constructed automaton
	 */
	public static SAuto motifRepeat(SAuto p) {
		SAuto auto = new SAuto();

		ArrayList<SState> newfinals;
		Hashtable<SState, SState> hash = new Hashtable<SState, SState>();
		for(SState s : p.states) {
			hash.put(s, auto.creatState());
		}

		SState tmpini = hash.get(p.init);
		auto.init = tmpini; // on reaffect en cas de probleme
		newfinals = searchMirrorsFinals(hash, p);

		//
		if(newfinals.size() != 1) {
			SState end = auto.creatState();
			auto.addFinalState(end);
			for(SState fin : newfinals) {
				new SEpsTransition(fin,end);
			}

			new SEpsTransition(tmpini,end);
			new SEpsTransition(end,tmpini);
		}
		else {// cas se produisant 100 pour cent des cas
			SState end = newfinals.get(0);
			auto.addFinalState(end);
			new SEpsTransition(tmpini,end);
			new SEpsTransition(end,tmpini);
		}

		return auto;
	}


	/**
	 * This method transform a string into an automaton that accept only the
	 * string which generating itself.
	 * @param str: string
	 * @return Return the constructed automaton
	 */
	public static SAuto convertStringToAuto(String str) {
		SAuto auto = new SAuto();
		SState etat = auto.creatState();
		for(int k=0; k < str.length();k++) {
			SState next = auto.creatState();
			new STransition(etat,next,new SGenericLetter(""+str.charAt(k)),1);
			etat = next;
		}
		auto.addFinalState(etat);
		return auto;
	}

	/**
	 * This method computes the subgraph of the automaton, with specific distance of the
	 * initial states.
	 * @param target: input automaton
	 * @param min: minimal distance from the initial state
	 * @param max: maximal distance from the initial state
	 * @return Return the automaton corresponding to the subgraph of target parameter
	 */
	public static SAuto subgraph(SAuto target,int min, int max) {
		SAuto auto = new SAuto();
		SState etat = auto.creatState();
		SState fin = auto.creatState();
		auto.addFinalState(fin);

		SState current = target.init;
		Hashtable<SState, SState> states = new Hashtable<SState, SState>();

		int pos = 0;

		Stack<Pair<SState, Integer>> pile = new Stack<Pair<SState,Integer>>();

		pile.push(new Pair<SState, Integer>(current,new Integer(pos)));

		do {
			Pair<SState, Integer> pair = pile.pop();
			current = pair.l();
			pos = pair.r().intValue();
			if(min == pos) {
				SState ss = getMirror(states, current, auto);
				new SEpsTransition(etat,ss);
			}

			if(max == pos) {
				SState ss = getMirror(states, current, auto);
				new SEpsTransition(ss,fin);
			}

			if((min <= pos) && (pos < max)) {
				Collection<STransition> trans = getAccessibleTransition(current);
				SState ss = getMirror(states, current, auto);

				for (STransition transition : trans) {
					SState sdest = getMirror(states,transition.getEnd() , auto);
					new STransition(ss,sdest,transition.getLetter(),transition.getRedundancy());
					pile.add(new Pair<SState, Integer>(transition.getEnd(),pos+1));
				}
			}

			if(pos < min) {
				Collection<STransition> trans = getAccessibleTransition(current);
				for (STransition transition : trans) {
					pile.add(new Pair<SState, Integer>(transition.getEnd(),pos+1));
				}
			}
		} while(pile.size() > 0);
		return auto;
	} 	

	private static SState getMirror(Hashtable<SState, SState> states,SState current,SAuto auto) {
		SState mirrorcurrent = null;
		if(states.containsKey(current))
			mirrorcurrent = states.get(current);
		else {
			mirrorcurrent = auto.creatState();
			states.put(current, mirrorcurrent);
		}
		return mirrorcurrent;		
	}


	/**
	 * This method search a random word from a specific automaton
	 * @param auto: the automaton
	 * @return Return the random string, or the empty string if an error occur.
	 * @throws TamagoCSPException 
	 */
	public static String searchRandomWord(SAuto auto) throws TamagoCSPException {
		// on s'arrure que l'auto n'est pas vide avec au moins 1 etat final
		if(auto.ids <= 1)
			throw new TamagoCSPException("Cannot generate word from an empty automaton");

		if(auto.finals.size() <= 0)
			throw new TamagoCSPException("Cannot generate word from an automaton with no final state");

		StringBuilder renvoie;
		SState state;
		boolean findFinalState = false;
		Random r = new Random();
		do {
			state = auto.init();
			renvoie = new StringBuilder();
			ArrayList<STransition> trans = (ArrayList<STransition>) getAccessibleTransition(state);
			while(trans.size() > 0) {
				if((auto.isFinalState(state)) && (r.nextFloat() <= 0.25)) 
					break;
				STransition t = trans.get(r.nextInt(trans.size()));
				renvoie.append(addEscapes(t.getLetter().select()));
				state = t.getEnd();
				trans = (ArrayList<STransition>) getAccessibleTransition(state);
			}
			TreeSet<SState> states = new TreeSet<SState>();
			getAccessibleState(states, state);
			for (SState state2 : states) {
				if(auto.isFinalState(state2)) {
					findFinalState = true;
					break;
				}
			}
		} while(!findFinalState);
		return renvoie.toString();
	}

	protected static final String addEscapes(char ch) {
		switch (ch) {
		case 0:
			return "\\0";
		case '\b':
			return ("\\b");
		case '\t':
			return ("\\t");
		case '\n':
			return ("\\n");
		case '\f':
			return ("\\f");
		case '\r':
			return("\\r");
		case '\"':
			return("\\\"");
		case '\'':
			return("\\\'");
		case '\\':
			return ("\\\\");
		default:
			if (((ch) < 0x20) || (ch > 0x7e)) {
				String s = "0000" + Integer.toString(ch, 16);
				return ("\\u"+ s.substring(s.length() - 4, s.length()));
			} else {
				return (""+ ch);
			}
		}
	}


	private static SState getOrCreat(Hashtable<SState, SState> hash, SAuto auto, SState a) {
		if(!hash.containsKey(a)) {
			SState assoc = auto.creatState();
			hash.put(a, assoc);
			return assoc;
		}
		else
			return hash.get(a);
	}

	private static boolean hasAccessibleFinalState(SAuto auto,SState a) {

		TreeSet<SState> set = new TreeSet<SState>();

		getAccessibleState(set, a);

		for (SState sState : set) {
			if(auto.isFinalState(sState))
				return true;
		}
		return false;
	}

	public static SAuto extractAuto(SAuto a, int min, int max) {
		SAuto res = new SAuto();
		Stack<Pair<Integer, SState>> pile = new Stack<Pair<Integer,SState>>();
		Hashtable<SState, SState> hash = new Hashtable<SState, SState>();

		SState init = res.creatState();
		SState end = res.creatState();
		res.addFinalState(end);

		pile.push(new Pair<Integer, SState>(0, a.init()));

		while(!pile.empty()) {
			Pair<Integer, SState> pair = pile.pop();
			SState current = pair.r();
			int profondeur = pair.l();

			SState mirrorA = null;
			if((min <= profondeur) && (profondeur <= max)) {
				mirrorA = getOrCreat(hash, res,current);
				if(min == profondeur)
					new SEpsTransition(init, mirrorA);
				if(max == profondeur)
					new SEpsTransition(mirrorA, end);
				if(hasAccessibleFinalState(a, current))
					res.addFinalState(mirrorA);
			}

			Collection<STransition> transitions = getAccessibleTransition(current); 

			boolean findRealTransition = false;
			for(STransition trans :  transitions) {
				SState mirrorB = null;
				if(trans.getBeg() == trans.getEnd()) {
					if((min <= profondeur) && (profondeur <= max))
						new STransition(mirrorA, mirrorA, trans.getLetter());
				}
				else {
					findRealTransition = true;
					if((min <= (profondeur+1)) && (profondeur+1 <= max)) {
						mirrorB = getOrCreat(hash, res, trans.getEnd());
					}
					if((mirrorA != null) && (mirrorB != null)) 
						new STransition(mirrorA, mirrorB, trans.getLetter());
					pile.push(new Pair<Integer, SState>(profondeur+1,trans.getEnd()));
				}

			}
			if((!findRealTransition) && (mirrorA != null)) {
				new SEpsTransition(mirrorA, end);
			}
		}
		return res;
	}

	public static void main(String[] args) {
		// exemple de these
		SAuto auto = new SAuto();

		SState[] e = new SState[10];
		for(int i=0; i < 10;i++) {
			e[i] = auto.creatState();
		}
		auto.addFinalState(e[9]);

		new STransition(e[0], e[1], new SGenericLetter("M"));
		new STransition(e[0], e[2], new SAnyLetter());

		new STransition(e[1], e[8], new SGenericLetter("r"));

		new STransition(e[2], e[3], new SGenericLetter("M"));
		new STransition(e[2], e[4], new SAnyLetter());

		new STransition(e[3], e[7], new SGenericLetter("r"));

		new STransition(e[4], e[6], new SGenericLetter("M"));
		new STransition(e[4], e[5], new SAnyLetter());

		new STransition(e[5], e[5], new SGenericLetter("M"));
		new STransition(e[5], e[6], new SAnyLetter());

		new STransition(e[6], e[7], new SGenericLetter("r"));

		new SEpsTransition(e[7], e[9]);

		new SEpsTransition(e[8], e[9]);

		new STransition(e[9], e[9], new SAnyLetter());

		try {
			new SPrintAutomaton(auto);
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}

		SAuto part2 = extractAuto(auto, 2, 3);
		try {
			new SPrintAutomaton(part2,"2 a 3");
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}

		SAuto part3 = extractAuto(auto, 2, 4);
		try {
			new SPrintAutomaton(part3, "2 a 4");
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}

		SAuto part = extractAuto(auto, 2, 5);
		try {
			new SPrintAutomaton(part,"2 a 5");
		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}
	}

	public static void essai() {
		SAuto autoa = motifChar(new SGenericLetter("ab"));
		SAuto autob = motifChar(new SGenericLetter("cde"));

		SAuto autoc = motifSequence(autoa, autob);
		SAuto autod = motifRepeat(autoc);
		SAuto autoe = motifSwitch(autoa,autob);
		SAuto concatene = null;

		try {
			new SPrintAutomaton(autoa,"[ab]");
		} catch (Exception e) {
			e.printStackTrace();
		}
		try {
			new SPrintAutomaton(autob,"[cde]");
		} catch (Exception e) {
			e.printStackTrace();
		}
		try {
			new SPrintAutomaton(autoc,"seq [ab][cde]");
		} catch (Exception e) {
			e.printStackTrace();
		}
		try {
			new SPrintAutomaton(autod,"repeat {[ab][cde]}*");
		} catch (Exception e) {
			e.printStackTrace();
		}
		try {
			new SPrintAutomaton(autoe,"switch [ab]|[cde]");
		} catch (Exception e) {
			e.printStackTrace();
		}

		try {
			SAuto auto =  SAutoFusion.fusion(autoa, autoe);
			new SPrintAutomaton(auto,"fusion [ab] & [ab]|[cde]");
		}
		catch(Exception e) {
			e.printStackTrace();
		}

		try {
			SAuto auto = SAutoFusion.fusion( autoc, autod);
			new SPrintAutomaton(auto,"fusion [ab][cde] & {[ab][cde]}*");
		}
		catch(Exception e) {
			e.printStackTrace();
		}

		try {
			SAuto[] auto = new SAuto[] {
					convertStringToAuto("Ale"),
					convertStringToAuto("ssan"),
					convertStringToAuto("dro")
			};
			concatene = motifSequence(auto[0], auto[1]);
			concatene = motifSequence(concatene, auto[2]);
			/*
			for (SAuto auto2 : auto) {
				new SPrintAutomaton(auto2,"fusion Alessandro");	
			}
			new SPrintAutomaton(concatene,"fusion Alessandro");
			 */
			System.err.println("=======================================ERL R");
			System.err.println(searchRandomWord(concatene));
			System.err.println("=======================================ELR D");

		}
		catch(Exception e) {
			e.printStackTrace();
		}

		String test[] = new String[] {
				"a",
				"ab",
				"ac",
				"acbdea",
				"acacacac",
				"c"
		};
		for(String t : test) {
			System.err.println(t);
			System.err.println("\t[ab]"+autoa.isAccepted(t));
			System.err.println("\t[cde]"+autob.isAccepted(t));
			System.err.println("\t[ab][cde]"+autoc.isAccepted(t));
			System.err.println("\t{[ab][cde]}*"+autod.isAccepted(t));
			System.err.println("\t[ab]|[cde]"+autoe.isAccepted(t));
		}

		try {
			for(int m = 0; m < 10; m++) {
				System.err.println("======================================="+m);
				System.err.println(searchRandomWord(autoa));
				System.err.println(searchRandomWord(autob));
				System.err.println(searchRandomWord(autoc));
				System.err.println(searchRandomWord(autod));
				System.err.println(searchRandomWord(autoe));
			}
		}catch(Exception excsd) {
			excsd.printStackTrace();
		}

		System.err.println("=======================================MIN LENGTH");
		System.err.println(evalMinSize(autoa));
		System.err.println(evalMinSize(autob));
		System.err.println(evalMinSize(autoc));
		System.err.println(evalMinSize(autod));
		System.err.println(evalMinSize(autoe));
		System.err.println(evalMinSize(concatene));
		System.err.println("=======================================MAX LENGTH");
		System.err.println(evalMaxSize(autoa));
		System.err.println(evalMaxSize(autob));
		System.err.println(evalMaxSize(autoc));
		System.err.println(evalMaxSize(autod));
		System.err.println(evalMaxSize(autoe));
		System.err.println(evalMaxSize(concatene));


	}
}
